{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Excellent Pairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #hash-table #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #哈希表 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countExcellentPairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #优质数对的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的正整数数组 <code>nums</code> 和一个正整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>如果满足下述条件，则数对 <code>(num1, num2)</code> 是 <strong>优质数对</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>num1</code> 和 <code>num2</code> <strong>都</strong> 在数组 <code>nums</code> 中存在。</li>\n",
    "\t<li><code>num1 OR num2</code> 和 <code>num1 AND num2</code> 的二进制表示中值为 <strong>1</strong> 的位数之和大于等于 <code>k</code> ，其中 <code>OR</code> 是按位 <strong>或</strong> 操作，而 <code>AND</code> 是按位 <strong>与</strong> 操作。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回 <strong>不同</strong> 优质数对的数目。</p>\n",
    "\n",
    "<p>如果&nbsp;<code>a != c</code> 或者 <code>b != d</code> ，则认为 <code>(a, b)</code> 和 <code>(c, d)</code> 是不同的两个数对。例如，<code>(1, 2)</code> 和 <code>(2, 1)</code> 不同。</p>\n",
    "\n",
    "<p><strong>注意：</strong>如果 <code>num1</code> 在数组中至少出现 <strong>一次</strong> ，则满足 <code>num1 == num2</code> 的数对 <code>(num1, num2)</code> 也可以是优质数对。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,1], k = 3\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>有如下几个优质数对：\n",
    "- (3, 3)：(3 AND 3) 和 (3 OR 3) 的二进制表示都等于 (11) 。值为 1 的位数和等于 2 + 2 = 4 ，大于等于 k = 3 。\n",
    "- (2, 3) 和 (3, 2)： (2 AND 3) 的二进制表示等于 (10) ，(2 OR 3) 的二进制表示等于 (11) 。值为 1 的位数和等于 1 + 2 = 3 。\n",
    "- (1, 3) 和 (3, 1)： (1 AND 3) 的二进制表示等于 (01) ，(1 OR 3) 的二进制表示等于 (11) 。值为 1 的位数和等于 1 + 2 = 3 。\n",
    "所以优质数对的数目是 5 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [5,1,1], k = 10\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>该数组中不存在优质数对。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 60</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-excellent-pairs](https://leetcode.cn/problems/number-of-excellent-pairs/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-excellent-pairs](https://leetcode.cn/problems/number-of-excellent-pairs/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,1]\\n3', '[5,1,1]\\n10']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        def count(x):\n",
    "            res = 0\n",
    "            while x:\n",
    "                x = x & (x - 1)\n",
    "                res += 1\n",
    "            return res\n",
    "        a = [0] * 61\n",
    "        s = set(nums)\n",
    "        for num in s:\n",
    "            a[count(num)] += 1\n",
    "        ans = 0\n",
    "        for i in range(61):\n",
    "            for j in range(61):\n",
    "                if i + j >= k:\n",
    "                    ans += a[i] * a[j]\n",
    "        return ans\n",
    "s = Solution()\n",
    "s.countExcellentPairs([1,2,3,1], 3)\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def func1(nums, k):\n",
    "    nums = set(nums)\n",
    "    lst = [bit_count(v) for v in nums]\n",
    "    dic = Counter(lst)\n",
    "    mylst = sorted(dic.items())\n",
    "\n",
    "    # 第一个用二分法查找\n",
    "    k1, n1 = mylst[-1]\n",
    "    tmp = k - k1\n",
    "    i = bisect_left(mylst, tmp, key=lambda x: x[0])\n",
    "    mylst = mylst[i:]\n",
    "\n",
    "    if 2 * k1 < k:\n",
    "        return 0\n",
    "\n",
    "    res = n1 * n1\n",
    "    mylst.pop()\n",
    "\n",
    "    for _, n2 in mylst:\n",
    "        res += n2 * n1 * 2\n",
    "\n",
    "    # 第二个开始\n",
    "    while mylst:\n",
    "        k1, n1 = mylst.pop()\n",
    "        tmp = k - k1\n",
    "\n",
    "        if 2 * k1 < k:\n",
    "            return res\n",
    "\n",
    "        while mylst:\n",
    "            k2, n2 = mylst[0]\n",
    "            if k2 >= tmp:\n",
    "                break\n",
    "            mylst.pop(0)\n",
    "\n",
    "        res += n1 * n1\n",
    "        for _, n2 in mylst:\n",
    "            res += n2 * n1 * 2\n",
    "    return res\n",
    "\n",
    "def bit_count(d):\n",
    "    res = 0\n",
    "    while d:\n",
    "        res += 1\n",
    "        d = d & (d - 1)\n",
    "    return res\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        return func1(nums,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        # ab and or 1 位数结果求和 等于 a和b的 1位数求和\n",
    "        # a∪b ∪ a∩b = a+b\n",
    "        cnt = Counter(num.bit_count() for num in set(nums))\n",
    "        ans = 0\n",
    "        for cx, ccx in cnt.items():\n",
    "            for cy, ccy in cnt.items():\n",
    "                if cx + cy >= k:\n",
    "                    ans += ccx * ccy\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "\n",
    "        cnt = [0] * 30\n",
    "        for x in set(nums):\n",
    "\n",
    "            cnt[x.bit_count()] += 1\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        s = sum(cnt[k:])\n",
    "\n",
    "        for cx, ccx in enumerate(cnt):\n",
    "\n",
    "            res += ccx * s\n",
    "\n",
    "            if 0 <= k - 1 - cx < 30:\n",
    "                s += cnt[k - 1 - cx]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        cnt = Counter(x.bit_count() for x in set(nums))\n",
    "        ans = 0\n",
    "        for cx, ccx in cnt.items():\n",
    "            for cy, ccy in cnt.items():\n",
    "                if cx + cy >= k:  # (x,y) 是优质数对\n",
    "                    ans += ccx * ccy\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter(x.bit_count() for x in set(nums))\n",
    "        for cx, ccx in cnt.items():\n",
    "            for cy, ccy in cnt.items():\n",
    "                if cx + cy >= k:\n",
    "                    ans += ccx * ccy\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        cnt = [0] * 30\n",
    "        for x in set(nums):\n",
    "            cnt[x.bit_count()] += 1\n",
    "        ans = 0\n",
    "        s = sum(cnt[k:])\n",
    "        for cx, ccx in enumerate(cnt):\n",
    "            # cx iters 0, 1, 2, ..., maxx\n",
    "            ans += ccx * s\n",
    "            if 0 <= k - 1 - cx < 30:\n",
    "                s += cnt[k - 1 - cx]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter(x.bit_count() for x in set(nums))\n",
    "        ans = 0\n",
    "        for cx, ccx in cnt.items():\n",
    "            for cy, ccy in cnt.items():\n",
    "                if cx + cy >= k:  # (x,y) 是优质数对\n",
    "                    ans += ccx * ccy\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        cnt=Counter(x.bit_count() for x in set(nums))\n",
    "        ans=0\n",
    "        for cx,ccx in cnt.items():\n",
    "            for cy,ccy in cnt.items():\n",
    "                if cx+cy>=k:\n",
    "                    ans+=ccx*ccy\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        bitCounter = Counter(n.bit_count() for n in set(nums))\n",
    "        bitSorted = sorted(bitCounter.keys())\n",
    "        res = sum(bitCounter[n]+bitCounter[n]*(bitCounter[n]-1) for n in bitSorted[bisect_left(bitSorted, k/2):])\n",
    "        for k1, k2 in combinations(bitSorted, 2):\n",
    "            if k1 + k2 >= k:\n",
    "                res += 2 * bitCounter[k1] * bitCounter[k2]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter(x.bit_count() for x in set(nums))\n",
    "        ans = 0 \n",
    "        for cx,ccx in cnt.items():\n",
    "            for cy,ccy in cnt.items():\n",
    "                if cx+cy>=k:\n",
    "                    ans += ccx*ccy\n",
    "                \n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = [0] * 30\n",
    "\n",
    "        # cnt 元素中1个数为i的元素频数\n",
    "        for num in set(nums):\n",
    "            cnt[num.bit_count()] += 1\n",
    "\n",
    "        s = sum(cnt[k:])\n",
    "        for i, c in enumerate(cnt):\n",
    "            ans += c * s\n",
    "            if 0 <= k-i-1 <30:\n",
    "                s += cnt[k-i-1]\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from bisect import bisect_left\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums = list(set(nums))\n",
    "        lst = [bit_count(v) for v in nums]\n",
    "        dic = Counter(lst)\n",
    "        mylst = sorted(dic.items())\n",
    "\n",
    "        # 第一个用二分法查找\n",
    "        k1, n1 = mylst[-1]\n",
    "        tmp = k - k1\n",
    "        i = bisect_left(mylst, tmp, key=lambda x: x[0])\n",
    "        mylst = mylst[i:]\n",
    "\n",
    "        if 2 * k1 < k:\n",
    "            return 0\n",
    "\n",
    "        res = n1 * n1\n",
    "        mylst.pop()\n",
    "\n",
    "        for _, n2 in mylst:\n",
    "            res += n2 * n1 * 2\n",
    "\n",
    "        # 第二个开始\n",
    "        while mylst:\n",
    "            k1, n1 = mylst.pop()\n",
    "            tmp = k - k1\n",
    "\n",
    "            if 2 * k1 < k:\n",
    "                return res\n",
    "\n",
    "            while mylst:\n",
    "                k2, n2 = mylst[0]\n",
    "                if k2 >= tmp:\n",
    "                    break\n",
    "                mylst.pop(0)\n",
    "\n",
    "            res += n1 * n1\n",
    "            for _, n2 in mylst:\n",
    "                res += n2 * n1 * 2\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "def bit_count(d):\n",
    "    res = 0\n",
    "    while d:\n",
    "        res += 1\n",
    "        d = d & (d - 1)\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        c = Counter(map(int.bit_count, set(nums)))\n",
    "        return sum(c[k1] * c[k2] for k1 in c for k2 in c if k1 + k2 >= k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter(x.bit_count() for x in set(nums))\n",
    "        ans = 0\n",
    "        for cx, ccx in cnt.items():\n",
    "            for cy, ccy in cnt.items():\n",
    "                if cx + cy >= k:  # (x,y) 是优质数对\n",
    "                    ans += ccx * ccy\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter(x.bit_count() for x in set(nums))\n",
    "        ans = 0\n",
    "        for cx, ccx in cnt.items():\n",
    "            for cy, ccy in cnt.items():\n",
    "                if cx + cy >= k:  # (x,y) 是优质数对\n",
    "                    ans += ccx * ccy\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        cnt=[0]*30\n",
    "        for x in set(nums):\n",
    "            cnt[x.bit_count()]+=1\n",
    "        s=sum(cnt[k:])\n",
    "        ans=0\n",
    "        for cx,ccx in enumerate(cnt):\n",
    "            ans+=s*ccx\n",
    "            if 0<=k-1-cx<30:\n",
    "                s+=cnt[k-1-cx]\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter(num.bit_count() for num in set(nums))\n",
    "        return sum(n0 * n1 for bit0, n0 in cnt.items() for bit1, n1 in cnt.items() if bit0 + bit1 >= k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        cnt = Counter(x.bit_count() for x in set(nums))\n",
    "        ans = 0\n",
    "        for cx, ccx in cnt.items():\n",
    "            for cy, ccy in cnt.items():\n",
    "                if cx + cy >= k:  # (x,y) 是优质数对\n",
    "                    ans += ccx * ccy\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        cnt = Counter()\n",
    "        ans = 0\n",
    "        nums = list(set(nums))\n",
    "        for num in nums:\n",
    "            cur = num.bit_count()\n",
    "            if cur * 2 >= k:\n",
    "                ans += 1\n",
    "            for ke, v in cnt.items():\n",
    "                if ke + cur >= k:\n",
    "                    ans += v * 2\n",
    "            cnt[cur] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        h = defaultdict(int)\n",
    "\n",
    "        nums = list(set(nums))\n",
    "\n",
    "        for num in nums:\n",
    "            num_bin = bin(num)[2:]\n",
    "            cnt = 0\n",
    "            for a in num_bin:\n",
    "                if a == \"1\":\n",
    "                    cnt += 1\n",
    "            h[cnt] += 1\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        print(h)\n",
    "\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            num_bin = bin(num)[2:]\n",
    "            cnt = 0\n",
    "            for a in num_bin:\n",
    "                if a == \"1\":\n",
    "                    cnt += 1\n",
    "            left = k - cnt\n",
    "            if left <= 0:\n",
    "                res += n\n",
    "                continue\n",
    "            \n",
    "            cur_cnt = 0\n",
    "            for i in range(left, 61):\n",
    "                if h[i] > 0:\n",
    "                    cur_cnt += h[i]\n",
    "            res += cur_cnt\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums = list(set(nums))\n",
    "        cnt = Counter()\n",
    "        maxx_k = -inf\n",
    "        ans = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            ki = num.bit_count()\n",
    "            if ki > maxx_k:\n",
    "                maxx_k = ki\n",
    "            iter_kj = k - ki\n",
    "            while iter_kj <= maxx_k:\n",
    "                ans += (cnt[iter_kj] * 2)\n",
    "                iter_kj += 1\n",
    "            cnt[ki] += 1\n",
    "            if ki * 2 >= k:\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        cnt = Counter()\n",
    "        nums = set(nums)\n",
    "        for num in nums:\n",
    "            cnt[num.bit_count()] += 1\n",
    "        ans = 0\n",
    "        for k0, v0 in cnt.items():\n",
    "            for k1, v1 in cnt.items():\n",
    "                if k0 + k1 >= k:\n",
    "                    ans += v0 * v1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\r\n",
    "        preCnt = [0] * 30\r\n",
    "        for num in set(nums):\r\n",
    "            preCnt[bin(num).count('1') - 1] += 1\r\n",
    "        \r\n",
    "        # preCnt[i] = number of integers in nums having more than i bitsets\r\n",
    "        for i in range(27, -1, -1):\r\n",
    "            preCnt[i] += preCnt[i + 1]\r\n",
    "        \r\n",
    "        print(preCnt)\r\n",
    "        res = 0\r\n",
    "        for i in range(max(1, k - 29), 30):\r\n",
    "        # number of integers having i bitsets\r\n",
    "            cnt = preCnt[i - 1] - preCnt[i]\r\n",
    "        # requires more than k - i - 1 bitsets to make a pair\r\n",
    "            res += cnt * preCnt[max(0, k - i - 1)]\r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums=list(set(nums))\n",
    "        nums.sort()\n",
    "        cnt=Counter()\n",
    "        res=0\n",
    "        for num in nums:\n",
    "            y=num.bit_count()\n",
    "            for i in range(k,61):\n",
    "                res+=2*cnt[i-y]\n",
    "            if 2*y>=k:\n",
    "                res+=1\n",
    "            cnt[y]+=1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        s = list(set(nums))\n",
    "        arr = [num.bit_count() for num in s]\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        ans = 0\n",
    "        l = 0\n",
    "        for r in range(n-1, -1, -1) :\n",
    "            while l < r and arr[l] + arr[r] < k :\n",
    "                l += 1\n",
    "            if arr[l] + arr[r] >= k :\n",
    "                ans += (r-l) * 2 + 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = [0] * 31\n",
    "        for x in set(nums):\n",
    "            cnt[x.bit_count()] += 1\n",
    "        for i in range(31):\n",
    "            for j in range(31):\n",
    "                if i + j >= k:\n",
    "                    ans += cnt[i] * cnt[j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums = list(set(nums))\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        \n",
    "        cnt = [0 for _ in range(33)]\n",
    "        #t = Counter(nums)\n",
    "        for i in range(n):\n",
    "            tmp = 0\n",
    "            for j in range(33):\n",
    "                if nums[i] & (1 << j):\n",
    "                    tmp += 1\n",
    "            cnt[tmp] += 1\n",
    "        for i in range(33):\n",
    "            for j in range(33):\n",
    "                if i + j >= k: \n",
    "                    ans += cnt[i] * cnt[j]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        cnt = Counter()\n",
    "        nums = set(nums)\n",
    "        for num in nums:\n",
    "            cnt[num.bit_count()] += 1\n",
    "        ans = 0\n",
    "        for k0, v0 in cnt.items():\n",
    "            for k1, v1 in cnt.items():\n",
    "                if v0 and v1 and k0 + k1 >= k:\n",
    "                    ans += v0 * v1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        cnt=Counter(x.bit_count() for x in set(nums))\n",
    "        ans=0\n",
    "        for cx,ccx in cnt.items():\n",
    "            for cy,ccy in cnt.items():\n",
    "                if cx+cy>=k:\n",
    "                    ans+=ccx*ccy\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        cnt = Counter()\n",
    "        nums = list(set(nums))\n",
    "        for num in nums:\n",
    "            cur = 0\n",
    "            for j in range(30):\n",
    "                if num & 1 << j:\n",
    "                    cur += 1\n",
    "            cnt[cur] += 1\n",
    "        ans = 0\n",
    "        for k0, v0 in cnt.items():\n",
    "            for k1, v1 in cnt.items():\n",
    "                if v0 and v1 and k0 + k1 >= k:\n",
    "                    if k0 == k1:\n",
    "                        ans += v0 * v0\n",
    "                    else:\n",
    "                        ans += v0 * v1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        # 对于一个数对 and+or 之后 1 的数量\n",
    "        # 等于 数对本身元素 1 的数量之和\n",
    "\n",
    "        # 因此 统计每个元素包含的1的数量 以及元素对应的频次 排列组合即可\n",
    "        cnt = Counter(num.bit_count() for num in set(nums))\n",
    "        print(cnt)\n",
    "        ans = 0\n",
    "        for cx, ccx in cnt.items():\n",
    "            for cy, ccy in cnt.items():\n",
    "                if cx + cy >= k:\n",
    "                    ans += ccx * ccy\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        bit_num = [bin(num).count('1') for num in set(nums)]\n",
    "        cnt = collections.Counter(bit_num)\n",
    "        res = 0\n",
    "        for i, v1 in cnt.items():\n",
    "            for j, v2 in cnt.items():\n",
    "                if i + j >= k:\n",
    "                    res += v1 * v2\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        h = defaultdict(int)\n",
    "\n",
    "        nums = list(set(nums))\n",
    "\n",
    "        for num in nums:\n",
    "            num_bin = bin(num)[2:]\n",
    "            cnt = 0\n",
    "            for a in num_bin:\n",
    "                if a == \"1\":\n",
    "                    cnt += 1\n",
    "            h[cnt] += 1\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            num_bin = bin(num)[2:]\n",
    "            cnt = 0\n",
    "            for a in num_bin:\n",
    "                if a == \"1\":\n",
    "                    cnt += 1\n",
    "            left = k - cnt\n",
    "            if left <= 0:\n",
    "                res += n\n",
    "                continue\n",
    "            \n",
    "            cur_cnt = 0\n",
    "            for i in range(left, 61):\n",
    "                if h[i] > 0:\n",
    "                    cur_cnt += h[i]\n",
    "            res += cur_cnt\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "def bit_count(d):\n",
    "    res = 0\n",
    "    while d:\n",
    "        res += 1\n",
    "        d = d & (d - 1)\n",
    "    return res\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        nums = list(set(nums))\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = bit_count(nums[i])\n",
    "        dic = Counter(nums)\n",
    "        mylst = sorted(dic.items())\n",
    "        a, b = mylst.pop()\n",
    "        num1 = k - a\n",
    "        pos = bisect_left(mylst, num1, key=lambda x: x[0])\n",
    "        mylst = mylst[pos:]\n",
    "        if 2 * a < k:\n",
    "            return res\n",
    "        res += b * b\n",
    "        for i, j in mylst:\n",
    "            res += j * b * 2\n",
    "        while mylst:\n",
    "            k1, n1 = mylst.pop()\n",
    "            tmp = k - k1\n",
    "            if 2 * k1 < k:\n",
    "                return res\n",
    "            res += n1 * n1\n",
    "            pos = bisect_left(mylst, tmp, key=lambda x: x[0])\n",
    "            mylst = mylst[pos:]\n",
    "            for i, j in mylst:\n",
    "                res += j * n1 * 2\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from bisect import bisect_left\n",
    "\n",
    "\n",
    "def func1(nums, k):\n",
    "    lst = [bit_count(v) for v in nums]\n",
    "    dic = Counter(lst)\n",
    "    mylst = sorted(dic.items())\n",
    "\n",
    "    # 第一个用二分法查找\n",
    "    k1, n1 = mylst[-1]\n",
    "    tmp = k - k1\n",
    "    i = bisect_left(mylst, tmp, key=lambda x: x[0])\n",
    "    mylst = mylst[i:]\n",
    "\n",
    "    if 2 * k1 < k:\n",
    "        return 0\n",
    "\n",
    "    res = n1 * n1\n",
    "    mylst.pop()\n",
    "\n",
    "    for _, n2 in mylst:\n",
    "        res += n2 * n1 * 2\n",
    "\n",
    "    # 第二个开始\n",
    "    while mylst:\n",
    "        k1, n1 = mylst.pop()\n",
    "        tmp = k - k1\n",
    "\n",
    "        if 2 * k1 < k:\n",
    "            return res\n",
    "\n",
    "        while mylst:\n",
    "            k2, n2 = mylst[0]\n",
    "            if k2 >= tmp:\n",
    "                break\n",
    "            mylst.pop(0)\n",
    "\n",
    "        res += n1 * n1\n",
    "        for _, n2 in mylst:\n",
    "            res += n2 * n1 * 2\n",
    "\n",
    "    return res\n",
    "\n",
    "\n",
    "def bit_count(d):\n",
    "    res = 0\n",
    "    while d:\n",
    "        res += 1\n",
    "        d = d & (d - 1)\n",
    "    return res\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums=set(nums)\n",
    "        return func1(nums,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums = set(nums)\n",
    "        def cntone(x):\n",
    "            ans = 0\n",
    "            while x:\n",
    "                if x & 1:\n",
    "                    ans += 1\n",
    "                x = x >> 1\n",
    "            return  ans\n",
    "        onenum = [cntone(x) for x in nums]\n",
    "        onenum.sort()\n",
    "        n = len(nums)\n",
    "        l, r = 0, n-1\n",
    "        ans = 0\n",
    "        while l < n:\n",
    "            t = onenum[l]\n",
    "            while r > 0 and onenum[r - 1] >= k - t:\n",
    "                r = r - 1\n",
    "            # print(r)\n",
    "            if onenum[l] + onenum[r] >= k:\n",
    "                ans += (n - r)\n",
    "            l += 1\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "def bit_count(d):\n",
    "    res = 0\n",
    "    while d:\n",
    "        res += 1\n",
    "        d = d & (d - 1)\n",
    "    return res\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        nums = list(set(nums))\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = bit_count(nums[i])\n",
    "        dic = Counter(nums)\n",
    "        mylst = sorted(dic.items())\n",
    "        a, b = mylst.pop()\n",
    "        num1 = k - a\n",
    "        pos = bisect_left(mylst, num1, key=lambda x: x[0])\n",
    "        mylst = mylst[pos:]\n",
    "        if 2 * a < k:\n",
    "            return res\n",
    "        res += b * b\n",
    "        for i, j in mylst:\n",
    "            res += j * b * 2\n",
    "        while mylst:\n",
    "            k1, n1 = mylst.pop()\n",
    "            tmp = k - k1\n",
    "            if 2 * k1 < k:\n",
    "                return res\n",
    "            res += n1 * n1\n",
    "            pos = bisect_left(mylst, tmp, key=lambda x: x[0])\n",
    "            mylst = mylst[pos:]\n",
    "            # while mylst:\n",
    "            #     k2, n2 = mylst[0]\n",
    "            #     if k2 >= tmp:\n",
    "            #         break\n",
    "            #     mylst.pop(0)\n",
    "            for i, j in mylst:\n",
    "                res += j * n1 * 2\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums = list(set(nums))\n",
    "        n = len(nums)\n",
    "        num1 = [0] * n\n",
    "        for i in range(n):\n",
    "            temp = nums[i]\n",
    "            while temp != 0:\n",
    "                num1[i] += temp % 2\n",
    "                temp //= 2\n",
    "        num1.sort()\n",
    "        num_pairs, right = 0, n - 1\n",
    "        for i in range(n):\n",
    "            while right != -1 and num1[i] + num1[right] >= k:\n",
    "                right -= 1\n",
    "            num_pairs += n - right - 1\n",
    "        return num_pairs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        cnt = [0] * 30\n",
    "        for x in set(nums):\n",
    "\n",
    "            cnt[x.bit_count()] += 1\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        s = sum(cnt[k:])\n",
    "\n",
    "        for cx, ccx in enumerate(cnt):\n",
    "\n",
    "            res += ccx * s\n",
    "\n",
    "            if 0 <= k - 1 - cx < 30:\n",
    "                s += cnt[k - 1 - cx]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums = list(set(nums))\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        cnt = [0 for _ in range(31)]\n",
    "        for i in range(n):\n",
    "            tmp = 0\n",
    "            for j in range(31):\n",
    "                if nums[i] & (1 << j):\n",
    "                    tmp += 1\n",
    "            cnt[tmp] += 1\n",
    "            \n",
    "        for i in range(31):\n",
    "            for j in range(31):\n",
    "                if i + j >= k: \n",
    "                    ans += cnt[i] * cnt[j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from bisect import bisect_left\n",
    "\n",
    "def bit_count(d):\n",
    "    res = 0\n",
    "    while d:\n",
    "        res += 1\n",
    "        d = d & (d - 1)\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums = set(nums)\n",
    "        lst = [bit_count(v) for v in nums]\n",
    "        dic = Counter(lst)\n",
    "        mylst = sorted(dic.items())\n",
    "\n",
    "        # 第一个用二分法查找\n",
    "        k1, n1 = mylst[-1]\n",
    "        tmp = k - k1\n",
    "        i = bisect_left(mylst, tmp, key=lambda x: x[0])\n",
    "        mylst = mylst[i:]\n",
    "\n",
    "        if 2 * k1 < k:\n",
    "            return 0\n",
    "\n",
    "        res = n1 * n1\n",
    "        mylst.pop()\n",
    "\n",
    "        for _, n2 in mylst:\n",
    "            res += n2 * n1 * 2\n",
    "\n",
    "        # 第二个开始\n",
    "        while mylst:\n",
    "            k1, n1 = mylst.pop()\n",
    "            tmp = k - k1\n",
    "\n",
    "            if 2 * k1 < k:\n",
    "                return res\n",
    "\n",
    "            while mylst:\n",
    "                k2, n2 = mylst[0]\n",
    "                if k2 >= tmp:\n",
    "                    break\n",
    "                mylst.pop(0)\n",
    "\n",
    "            res += n1 * n1\n",
    "            for _, n2 in mylst:\n",
    "                res += n2 * n1 * 2\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\r\n",
    "        # popcount(a & b + a | b) = popcount(a) + popcount(b)\r\n",
    "        preCnt = [0] * 30\r\n",
    "        for num in set(nums):\r\n",
    "            preCnt[bin(num).count('1') - 1] += 1\r\n",
    "        \r\n",
    "        # preCnt[i] = number of integers in nums having more than i bitsets\r\n",
    "        for i in range(27, -1, -1):\r\n",
    "            preCnt[i] += preCnt[i + 1]\r\n",
    "        \r\n",
    "        res = 0\r\n",
    "        for i in range(max(1, k - 29), 30):\r\n",
    "        # number of integers having i bitsets\r\n",
    "            cnt = preCnt[i - 1] - preCnt[i]\r\n",
    "        # requires more than k - i - 1 bitsets to make a pair\r\n",
    "            res += cnt * preCnt[max(0, k - i - 1)]\r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums = list(set(nums))\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        \n",
    "        cnt = [0 for _ in range(33)]\n",
    "        #t = Counter(nums)\n",
    "        for i in range(n):\n",
    "            tmp = 0\n",
    "            for j in range(33):\n",
    "                if nums[i] & (1 << j):\n",
    "                    tmp += 1\n",
    "            cnt[tmp] += 1\n",
    "        for i in range(33):\n",
    "            for j in range(33):\n",
    "                if i + j >= k:\n",
    "                    if i == j:\n",
    "                        ans += cnt[i] * cnt[j]\n",
    "                    else:\n",
    "                        ans += cnt[i] * cnt[j]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from bisect import bisect_left\n",
    "\n",
    "\n",
    "def func1(nums, k):\n",
    "    lst = [bit_count(v) for v in nums]\n",
    "    dic = Counter(lst)\n",
    "    mylst = sorted(dic.items())\n",
    "\n",
    "    # 第一个用二分法查找\n",
    "    k1, n1 = mylst[-1]\n",
    "    tmp = k - k1\n",
    "    i = bisect_left(mylst, tmp, key=lambda x: x[0])\n",
    "    mylst = mylst[i:]\n",
    "\n",
    "    if 2 * k1 < k:\n",
    "        return 0\n",
    "\n",
    "    res = n1 * n1\n",
    "    mylst.pop()\n",
    "\n",
    "    for _, n2 in mylst:\n",
    "        res += n2 * n1 * 2\n",
    "\n",
    "    # 第二个开始\n",
    "    while mylst:\n",
    "        k1, n1 = mylst.pop()\n",
    "        tmp = k - k1\n",
    "\n",
    "        if 2 * k1 < k:\n",
    "            return res\n",
    "\n",
    "        while mylst:\n",
    "            k2, n2 = mylst[0]\n",
    "            if k2 >= tmp:\n",
    "                break\n",
    "            mylst.pop(0)\n",
    "\n",
    "        res += n1 * n1\n",
    "        for _, n2 in mylst:\n",
    "            res += n2 * n1 * 2\n",
    "\n",
    "    return res\n",
    "\n",
    "\n",
    "def bit_count(d):\n",
    "    res = 0\n",
    "    while d:\n",
    "        res += 1\n",
    "        d = d & (d - 1)\n",
    "    return res\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums=set(nums)\n",
    "        return func1(nums,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def bit_count(d):\n",
    "    res = 0\n",
    "    while d:\n",
    "        res += 1\n",
    "        d = d & (d - 1)\n",
    "    return res\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums=set(nums)\n",
    "        lst = [bit_count(v) for v in nums]\n",
    "        dic = Counter(lst)\n",
    "        mylst = sorted(dic.items())\n",
    "\n",
    "        # 第一个用二分法查找\n",
    "        k1, n1 = mylst[-1]\n",
    "        tmp = k - k1\n",
    "        i = bisect_left(mylst, tmp, key=lambda x: x[0])\n",
    "        mylst = mylst[i:]\n",
    "\n",
    "        if 2 * k1 < k:\n",
    "            return 0\n",
    "\n",
    "        res = n1 * n1\n",
    "        mylst.pop()\n",
    "\n",
    "        for _, n2 in mylst:\n",
    "            res += n2 * n1 * 2\n",
    "\n",
    "        # 第二个开始\n",
    "        while mylst:\n",
    "            k1, n1 = mylst.pop()\n",
    "            tmp = k - k1\n",
    "\n",
    "            if 2 * k1 < k:\n",
    "                return res\n",
    "\n",
    "            while mylst:\n",
    "                k2, n2 = mylst[0]\n",
    "                if k2 >= tmp:\n",
    "                    break\n",
    "                mylst.pop(0)\n",
    "\n",
    "            res += n1 * n1\n",
    "            for _, n2 in mylst:\n",
    "                res += n2 * n1 * 2\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums=list(set(nums))\n",
    "        n=len(nums)\n",
    "        s=SortedList()\n",
    "        a=[bin(nums[i]).count('1') for i in range(n)]\n",
    "        ans=0\n",
    "        for x in a:\n",
    "            if x+x>=k:\n",
    "                ans+=1\n",
    "            if len(s)>0:\n",
    "                diff=max(0,k-x)\n",
    "                index=s.bisect_left(diff)\n",
    "                ans+=(len(s)-index)*2\n",
    "            s.add(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums = set(nums)\n",
    "        n = len(nums)\n",
    "        cnt = [0]*n\n",
    "        i = 0\n",
    "        for num in nums:\n",
    "            cnt[i] = bin(num).replace('0b','').count('1')\n",
    "            i += 1\n",
    "        # print(nums)\n",
    "        # print(cnt)\n",
    "        if max(cnt)<k//2:\n",
    "            return 0\n",
    "        ans = n**2\n",
    "        a = Counter(cnt)\n",
    "        for j in range(k):\n",
    "            for i in range(k-j):\n",
    "                ans -= a[i]*a[j]\n",
    "        # print(a)\n",
    "        # for i in range(n):\n",
    "        #     if cnt[i]+cnt[0]>=k:\n",
    "        #         ans += (n-i)*n\n",
    "        #         break\n",
    "        #     for j in range(n):\n",
    "        #         if cnt[i]+cnt[j]>=k:\n",
    "        #             ans += n-j\n",
    "        #             break\n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums=list(set(nums))\n",
    "        n=len(nums)\n",
    "        s=SortedList()\n",
    "        a=[bin(nums[i]).count('1') for i in range(n)]\n",
    "        ans=0\n",
    "        for x in a:\n",
    "            if x+x>=k:\n",
    "                ans+=1\n",
    "            if len(s)>0:\n",
    "                diff=max(0,k-x)\n",
    "                index=s.bisect_left(diff)\n",
    "                ans+=(len(s)-index)*2\n",
    "            s.add(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums=set(nums)\n",
    "        n=len(nums)\n",
    "        s=SortedList()\n",
    "        a=[bin(num).count('1') for num in nums]\n",
    "        ans=0\n",
    "        for x in a:\n",
    "            if x+x>=k:\n",
    "                ans+=1\n",
    "            if len(s)>0:\n",
    "                diff=max(0,k-x)\n",
    "                index=s.bisect_left(diff)\n",
    "                ans+=(len(s)-index)*2\n",
    "            s.add(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums=set(nums)\n",
    "        n=len(nums)\n",
    "        s=SortedList()\n",
    "        a=[bin(num).count('1') for num in nums]\n",
    "        ans=0\n",
    "        for x in a:\n",
    "            if x+x>=k:\n",
    "                ans+=1\n",
    "            if len(s)>0:\n",
    "                diff=max(0,k-x)\n",
    "                index=s.bisect_left(diff)\n",
    "                ans+=(len(s)-index)*2\n",
    "            s.add(x)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
